package 力扣_树算法.搜索树;

public class 将有序数组转换为二叉搜索树_108 {
    /**
     给定二叉搜索树的中序遍历,不能唯一地确定二叉搜索树,如果没有要求二叉搜索树的高度平衡.
     则任何一个数字都可以作为二叉搜索树的根节点,因此可能的二叉搜索树有多个.
     二叉搜索树的高度平衡也不能唯一地确定二叉搜索树.
     直观地看,可以选择中间数字作为二叉搜索树的根节点,这样分给左右子树的数字个数相同或只相差1,可以使得树保持平衡.
     如果数组长度是奇数,则根节点的选择是唯一的,如果数组长度是偶数
     则可以选择中间位置左边的数字作为根节点或者选择中间位置右边的数字作为根节点
     选择不同的数字作为根节点则创建的平衡二叉搜索树也是不同的.
     */
    /**
     BST的中序遍历是升序的,因此本题等同于根据中序遍历的序列恢复二叉搜索树.
     因此可以以升序序列中的任一个元素作为根节点,以该元素左边的升序序列构建左子树,以该元素右边的升序序列构建右子树
     这样得到的树就是一棵二叉搜索树,又因为本题要求高度平衡,因此要选择升序序列的中间元素作为根节点
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return builder(nums, 0, nums.length - 1);
    }
    private TreeNode builder(int[] nums, int left, int right){
        if (left > right) {
            return null;
        }
        // 总是选择中间位置左边的数字作为根节点
        int mid = left + ((right - left) >> 1);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = builder(nums, left, mid - 1);
        root.right = builder(nums, mid + 1, right);
        return root;
    }
}
